#include <iostream>

#include <vector>
#include <string>

using namespace std;

int getLongestPublicSequenceLength(string A, string B) {
    int n = A.length();
    int m = B.length();
    
    // 创建二维数组存储子问题的最优解
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    
    // 动态规划计算最长公共子序列
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A[i - 1] == B[j - 1]) {
                // 如果字符匹配，长度加1
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 如果字符不匹配，取跳过A[i]或跳过B[j]的最大值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[n][m];
}

// vector<int> getAllSequenceLength(string str) {
//     vector<int> re;

//     return re;
// }

// int dp(vector<int> n, vector<int> m) {
//     return 0;
// }

void test01() {
    // 测试用例1：基础示例
    string A1 = "abcde";
    string B1 = "acde";
    int result1 = getLongestPublicSequenceLength(A1, B1);
    cout << "测试1 - A: \"" << A1 << "\", B: \"" << B1 << "\"" << endl;
    cout << "最长公共子序列长度: " << result1 << endl;
    cout << "预期结果: 4" << endl;
    cout << (result1 == 4 ? "✓ 通过" : "✗ 失败") << endl << endl;
}

void test02() {
    // 测试用例2：无公共子序列
    string A2 = "abc";
    string B2 = "xyz";
    int result2 = getLongestPublicSequenceLength(A2, B2);
    cout << "测试2 - A: \"" << A2 << "\", B: \"" << B2 << "\"" << endl;
    cout << "最长公共子序列长度: " << result2 << endl;
    cout << "预期结果: 0" << endl;
    cout << (result2 == 0 ? "✓ 通过" : "✗ 失败") << endl << endl;
}

void test03() {
    // 测试用例3：完全相同
    string A3 = "hello";
    string B3 = "hello";
    int result3 = getLongestPublicSequenceLength(A3, B3);
    cout << "测试3 - A: \"" << A3 << "\", B: \"" << B3 << "\"" << endl;
    cout << "最长公共子序列长度: " << result3 << endl;
    cout << "预期结果: 5" << endl;
    cout << (result3 == 5 ? "✓ 通过" : "✗ 失败") << endl << endl;
}

void test04() {
    // 测试用例4：一个字符串为空
    string A4 = "abc";
    string B4 = "";
    int result4 = getLongestPublicSequenceLength(A4, B4);
    cout << "测试4 - A: \"" << A4 << "\", B: \"\"" << endl;
    cout << "最长公共子序列长度: " << result4 << endl;
    cout << "预期结果: 0" << endl;
    cout << (result4 == 0 ? "✓ 通过" : "✗ 失败") << endl << endl;
}

void test05() {
    // 测试用例5：复杂情况
    string A5 = "ABCDGH";
    string B5 = "AEDFHR";
    int result5 = getLongestPublicSequenceLength(A5, B5);
    cout << "测试5 - A: \"" << A5 << "\", B: \"" << B5 << "\"" << endl;
    cout << "最长公共子序列长度: " << result5 << endl;
    cout << "预期结果: 3 (ADH)" << endl;
    cout << (result5 == 3 ? "✓ 通过" : "✗ 失败") << endl << endl;
}

void test06() {
    // 测试用例6：随机字符
    string A6 = "AGGTAB";
    string B6 = "GXTXAYB";
    int result6 = getLongestPublicSequenceLength(A6, B6);
    cout << "测试6 - A: \"" << A6 << "\", B: \"" << B6 << "\"" << endl;
    cout << "最长公共子序列长度: " << result6 << endl;
    cout << "预期结果: 4 (GTAB)" << endl;
    cout << (result6 == 4 ? "✓ 通过" : "✗ 失败") << endl << endl;
}

void test07() {
    // 测试用例7：中文测试
    string A7 = "你好世界";
    string B7 = "世界你好";
    int result7 = getLongestPublicSequenceLength(A7, B7);
    cout << "测试7 - A: \"" << A7 << "\", B: \"" << B7 << "\"" << endl;
    cout << "最长公共子序列长度: " << result7 << endl;
    cout << "预期结果: 2 (你好 或 世界)" << endl;
    cout << (result7 >= 2 ? "✓ 通过" : "✗ 失败") << endl << endl;
}

int main() {
    cout << "==================================================" << endl;
    cout << "最长公共子序列 (LCS) 算法测试" << endl;
    cout << "==================================================" << endl << endl;
    
    // 运行所有测试
    test01();
    test02();
    test03();
    test04();
    test05();
    test06();
    test07();
    
    cout << "==================================================" << endl;
    cout << "所有测试完成！" << endl;
    cout << "==================================================" << endl;
    
    return 0;
}
